package com.njupt.graphTheory;


import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/1/30 10:52
 * @Description: 深度优先遍历邻接表法
 * @Version: 1.0
 */


public class DeepFirstTraversal_AdjacencyList {

    /**
     * 写法一：从已知节点到目的节点的所有可达路径
     * 这里的x为起始节点
     *
     * @param graph
     * @param x       其实节点
     * @param n       终止节点
     * @param result
     * @param results
     */
    public static void dfs(List<LinkedList<Integer>> graph, int x, int n, List<Integer> result, List<List<Integer>> results) {

        if (x == n) {
            results.add(new ArrayList<>(result));
            return;
        }

        for (int num : graph.get(x)) {
            result.add(num);
            dfs(graph, num, n, result, results);
            result.remove(result.size() - 1);
        }
    }

    /**
     * 更加一般深度遍历的写法
     *
     * @param graph     传入一张图
     * @param isVisited 记录是否已经遍历
     * @param node      开始遍历的第一个结果
     * @param result    结果集
     */
    public static void dfs1(List<List<Integer>> graph, boolean[] isVisited, int node, List<Integer> result) {
        result.add(node);
        isVisited[node] = true;
        for (Integer v : graph.get(node)) {
            if (!isVisited[v]) {
                dfs1(graph, isVisited, v, result);
            }
        }
    }

    /**
     * 更加一般的广度优先遍历写法
     * @param graph
     * @param isVisited
     * @param node
     * @param queue
     */
    public static void bfs(List<List<Integer>> graph, boolean[] isVisited, int node, Deque<Integer> queue) {
        queue.add(node);
        isVisited[node] = true;
        while (!queue.isEmpty()) {
            Integer v = queue.pollFirst();
            System.out.println(v);
            isVisited[v] = true;
            for (Integer u : graph.get(v)) {
                if (!isVisited[u]) {
                    queue.add(u);
                }
            }
        }
    }

    public static void main(String[] args) {

        List<List<Integer>> graph = new ArrayList<>();
        List<Integer> l0 = new LinkedList<>();
        l0.add(1);
        l0.add(3);

        List<Integer> l1 = new LinkedList<>();
        l1.add(2);
        l1.add(4);

        List<Integer> l2 = new LinkedList<>();
        l2.add(3);

        List<Integer> l3 = new LinkedList<>();

        List<Integer> l4 = new LinkedList<>();
        l4.add(5);

        List<Integer> l5 = new LinkedList<>();

        graph.add(l0);
        graph.add(l1);
        graph.add(l2);
        graph.add(l3);
        graph.add(l4);
        graph.add(l5);

        boolean[] isVisited = new boolean[6];
        List<Integer> result = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < 6; i++) {
            if (!isVisited[i]) {
//                dfs1(graph,isVisited,0,result);

//                bfs(graph, isVisited, i, queue);


            }

        }

//        System.out.println(result);
    }
}
